<TITLE>prob014: Solitaire Battleships</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob014: Solitaire Battleships</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.dcs.st-and.ac.uk/~ipg/">
          <B>Ian Gent</B></A>
          <ADDRESS><a href="mailto:ipg@dcs.st-and.ac.uk">
          ipg@dcs.st-and.ac.uk</a></ADDRESS>
</TABLE>
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Specification </H3>

The Battleships puzzle is occasionally published in  Games Magazine (US),
e.g. in the August 1998 issue where it is credited
to Mark Gottlieb.   It is loosely based on
the two person pencil and paper game.
I quote the puzzle description in the magazine: 

<P>

<TT>
This fleet consists of one battleship (four grid squares in length), 
two cruisers (each three grid squares long), three 
three destroyers (each two squares long) and 
four submarines (one square each).  The ships may be oriented
horizontally or vertically, and no two ships will occupy adjacent grid
squares, not even diagonally.  The digits along the right side of and 
below the grid indicate the number of grid squares in the corresponding
rows and columns that are occupied by vessels. 
<P>
In each of the puzzles, one or more `shots' have been taken to start you off.
These may show water (indicated by wavy lines), a complete submarine 
(a circle), or the middle (a square), or the end (a rounded-off square) of 
a longer vessel. 
</TT>

<P>
Here is an example problem, the first from that issue of the magazine:
<pre>
  -------------------
0|                   |
2|                   |
3|                   |
1|                   |
2|                   |
4|                   |
2|                   |
1|o                  |
2|                   |
3|                   |
 --------------------
  1 3 3 1 5 1 2 4 0 0 
</pre>

The `o' in the grid indicates a submarine must occupy that square.

<P>
Published puzzles all have a grid of 10x10 and the ships as described 
above.  Of course there is no reason that these properties cannot be 
varied. 


<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="index.html">Overview page for this problem</A>
<P>
 <A HREF="../../index.html"> Back</A> to CSPLib home page.



